package com.sakura.二叉树;

import java.util.ArrayDeque;
import java.util.Deque;

public class Code530_二叉搜索树的最小绝对差 {

    // Definition for a binary tree node.
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public int getMinimumDifference(TreeNode root) {
        if (root == null) return 0;
        in(root);
        return ans;
    }

    private TreeNode pre = null;
    private int ans = Integer.MAX_VALUE;
    public void in(TreeNode cur) {
        if (cur == null) return;
        in(cur.left);
        if (pre != null) {
            ans = Math.min(ans, cur.val - pre.val);
        }
        pre = cur;
        in(cur.right);
    }

    // 迭代
    private static Deque<TreeNode> stack = new ArrayDeque<>();
    public int getMinimumDifference_2(TreeNode root) {
        if (root == null) return 0;
        TreeNode pre = null;
        int ans = Integer.MAX_VALUE;
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                 cur = stack.pop();
                 if (pre != null) {
                     ans = Math.min(ans, cur.val - pre.val);
                 }
                 pre = cur;
                 cur = cur.right;
            }
        }
        return ans;
    }


}
